package com.huangpeng.designmodel.algorithm;

import exception.CommonException;
import org.springframework.util.ObjectUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Objects;

/**
 * @Author huangpeng
 * @Title 排序算法
 * @Package
 * @Date 2021/1/26 10:48
 * @Description
 * @Version 1.0
 * 总结（选择排序算法准则）
 * 每种排序算法都各有优缺点。因此，在实用时需根据不同情况适当选用，甚至可以将多种方法结合起来使用。
 * 影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法时还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下四点：
 *
 * 1．待排序的记录数目n的大小；
 * 2．记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；
 * 3．关键字的结构及其分布情况；
 * 4．对排序稳定性的要求。 设待排序元素的个数为n。
 * （1）当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
 * 快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
 * 堆排序：如果内存空间允许且要求稳定性的；
 * 归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。
 *
 * （2）当n较大，内存空间允许，且要求稳定性，推荐归并排序
 *
 * （3）当n较小，可采用直接插入或直接选择排序。直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序
 *
 * （4）一般不使用或不直接使用传统的冒泡排序。
 *
 * （5）基数排序它是一种稳定的排序算法，但有一定的局限性：　　
 * 1、关键字可分解。　　
 * 2、记录的关键字位数较少，如果密集更好　　
 * 3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。
 */
public class Sort {
    public static void main(String[] args) {
        int[] data = {1,4,43,23,45,2,3,5,7,7,8,9,77,0,22,6,12,16,67,43};
        //bubbleSort(data);
        //selectionSort(data);
        //insertionSort(data);
        //shellSort(data);
        //sort(data,1,10);
        //quickSort(data,4,10);
        //heapSort(data);
        //countingSort(data,77);
        //bucketSort(data);
        radixSort(data,5,77);
    }

    /**
     * 冒泡排序（Bubble Sort）
     *      * 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
     *      * 算法描述  比较相邻的元素。如果第一个比第二个大，就交换它们两个； 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； 针对所有的元素重复以上的步骤，除了最后一个； 重复步骤1~3，直到排序完成。
     * @param data
     */
    public static void bubbleSort(int data[]){
        if(Objects.isNull(data)){
            throw new CommonException("data must not be null");
        }
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < data.length - 1; i++) {
            for (int j = 0; j < data.length - i - 1; j++) {
                if(data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println("冒泡排序>>>程序运行时间：" + (endTime - startTime) + "ms");
        System.out.println(Arrays.toString(data));
        System.out.println();
    }

    /**
     * 选择排序（Selection Sort）
     *      * 选择排序(Selection - sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
     *      * 算法描述  n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。
     *      * 具体算法描述如下：
     *      * 初始状态：无序区为R[1…n]，有序区为空；
     *      * 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
     *      * n-1趟结束，数组有序化了。
     *      * 算法分析
     *      * 表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
     * @param data
     */
    public static void selectionSort(int data[]){
        int minIndex;
        int temp;
        if(ObjectUtils.isEmpty(data)){
            throw new CommonException("data must not be null");
        }
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < data.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < data.length; j++) {
                if(data[j] < data[minIndex]){//寻找最小的数
                    minIndex = j;
                }
            }
            temp = data[i];
            data[i] = data[minIndex];
            data[minIndex] = temp;
        }
        long endTime = System.currentTimeMillis();
        System.out.println();
        System.out.println("选择排序>>>程序运行时间：" + (endTime - startTime) + "ms");
        System.out.println(Arrays.toString(data));
        System.out.println();
    }

    /**
     * 插入排序（Insertion Sort）
     * 插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
     * 算法描述
     * 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
     * 从第一个元素开始，该元素可以认为已经被排序；
     * 取出下一个元素，在已经排序的元素序列中从后向前扫描；
     * 如果该元素（已排序）大于新元素，将该元素移到下一位置；
     * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
     * 将新元素插入到该位置后；
     * 重复步骤2~5。
     * 算法分析
     * 插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
     * @param data
     */
    public static void insertionSort(int data[]){
        int preIndex;
        int current;
        if(ObjectUtils.isEmpty(data)){
            throw new CommonException("data must not be null");
        }
        long startTime = System.currentTimeMillis();
        for (int i = 1; i < data.length; i++) {
            preIndex = i - 1;
            current = data[i];
            for (; preIndex >= 0 && data[preIndex] > current; preIndex --){
                data[preIndex + 1] = data[preIndex];
            }
            data[preIndex + 1] = current;
        }
        long endTime = System.currentTimeMillis();
        System.out.println();
        System.out.println("插入排序>>>程序运行时间：" + (endTime - startTime) + "ms");
        System.out.println(Arrays.toString(data));
        System.out.println();
    }

    /**
     * 希尔排序（Shell Sort）
     * 1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
     * 算法描述
     * 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
     * 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
     * 按增量序列个数k，对序列进行k 趟排序；
     * 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
     * 算法分析
     * 希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。
     * @param data
     */
    public static void shellSort(int data[]){
        if(ObjectUtils.isEmpty(data)){
            throw new CommonException("data must not be null");
        }
        int temp;
        //增量
        int incrementNum = data.length / 2;
        long startTime = System.currentTimeMillis();
        while (incrementNum >= 1){
            for (int i = 0; i < data.length; i++) {
                //进行插入排序
                for (int j = i; j < data.length - incrementNum; j = j + incrementNum) {
                    if(data[j] > data[j + incrementNum]){
                        temp = data[j];
                        data[j] = data[j + incrementNum];
                        data[j + incrementNum] = temp;
                    }
                }
            }
            //设置新的增量
            incrementNum = incrementNum / 2;
        }
        long endTime = System.currentTimeMillis();
        System.out.println();
        System.out.println("希尔排序>>>程序运行时间：" + (endTime - startTime) + "ms");
        System.out.println(Arrays.toString(data));
        System.out.println();
    }

    /**
     * 归并排序（Merge Sort）
     * 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
     * 算法描述
     * 把长度为n的输入序列分成两个长度为n/2的子序列；
     * 对这两个子序列分别采用归并排序；
     * 将两个排序好的子序列合并成一个最终的排序序列。
     * 算法分析
     * 归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。
     * @param data
     * @param start
     * @param mid
     * @param end
     * 将两个有序序列归并为一个有序序列(二路归并)
     */
    public static void mergerSort(int data[], int start,int mid,int end){
        int[] array = new int[end + 1];// 定义一个临时数组，用来存储排序后的结果
        int low = start;
        int left = start;
        int center = mid + 1;
        long startTime = System.currentTimeMillis();
        // 取出最小值放入临时数组中
        while (start <= mid && center <= end){
            array[low ++] = data[start] > data[center] ? data[center ++] : data[start ++];
        }
        // 若还有段序列不为空，则将其加入临时数组末尾
        while (start <= mid){
            array[low ++] = data[start ++];
        }
        while (center <= end){
            array[low ++] = data[center ++];
        }
        // 将临时数组中的值copy到原数组中
        for (int i = left; i < end; i++) {
            data[i] = array[i];
        }
        long endTime = System.currentTimeMillis();
        System.out.println();
        System.out.println("归并排序>>>程序运行时间：" + (endTime - startTime) + "ms");
        System.out.println(Arrays.toString(data));
        System.out.println();
    }
    public static void sort(int data[], int start, int end){
        if(ObjectUtils.isEmpty(data)){
            throw new CommonException("data must not be null");
        }
        if (start > end){
            throw new CommonException("start must less than end");
        }
        int mid = (start + end) / 2;
        // 递归实现归并排序
        //sort(data,start,mid);
        //sort(data,mid + 1,end);
        mergerSort(data,start,mid,end);
    }

    /**
     * 快速排序（Quick Sort）
     * 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
     * 算法描述
     * 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
     * 从数列中挑出一个元素，称为 “基准”（pivot）；
     * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
     * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
     * @param data
     * @param low
     * @param high
     */
    public static void quickSort(int data[], int low, int high){
        if(ObjectUtils.isEmpty(data)){
            throw new CommonException("data must not be null");
        }
        long startTime = System.currentTimeMillis();
        int start = low;
        int end = high;
        int key = data[low];
        while (start < end){
            //从后往前比较
            while (start < end && data[end] >= key){//如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                end --;
                if(data[end] <= key){
                    int temp = data[end];
                    data[end] = data[start];
                    data[start] = temp;
                }
            }
            //从前往后比较
            while (start < end && data[end] <= key){//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                start ++;
                if(data[start] >= key){
                    int temp = data[start];
                    data[start] = data[end];
                    data[end] = temp;
                }
            }
        }
        //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
        //递归完成排序
        if(start > low){
            quickSort(data,low,start - 1);
        }
        if(end < high){
            quickSort(data,end + 1,high);
        }
        long endTime = System.currentTimeMillis();
        System.out.println();
        System.out.println("快速排序>>>程序运行时间：" + (endTime - startTime) + "ms");
        System.out.println(Arrays.toString(data));
        System.out.println();
    }

    /**
     * 堆排序（Heap Sort）
     * 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。（若想升序则建立大根堆，若想降序，则建立小根堆）
     * 算法描述
     * 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
     * 交换堆顶的元素和最后一个元素，此时最后一个位置作为有序区（有序区显示为黄色），然后进行其他无序区的堆调整，重新得到大顶堆后，交换堆顶和倒数第二个元素的位置……；
     * 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
     * @param data
     *
     */
    public static void heapSort(int data[]){
        if(ObjectUtils.isEmpty(data)){
            throw new CommonException("data must not be null");
        }
        int len = data.length;
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < len - 1; i++) {
            buildHeap(data,len - 1 - i);
            swap(data,0,len - 1 - i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println();
        System.out.println("堆排序>>>程序运行时间：" + (endTime - startTime) + "ms");
        System.out.println(Arrays.toString(data));
        System.out.println();
    }
    /**
     * 建立堆，在数组data中，从0到lastIndex建立堆
     * @param data
     * @param lastIndex
     */
    public static void buildHeap(int data[], int lastIndex){
        for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
            //k保存正在判断的节点
            int k = i;
            while (2 * k + 1 <= lastIndex){
                int biggerIndex = 2 * k + 1;
                if(biggerIndex < lastIndex){
                    if(data[biggerIndex] < data[biggerIndex + 1]){
                        biggerIndex ++;
                    }
                }
                if(data[k] < data[biggerIndex]){
                    swap(data,k,biggerIndex);
                    k = biggerIndex;
                }else{
                    break;
                }
            }
        }
    }
    /**
     * 交换元素的函数
     * @param data
     * @param i
     * @param j
     */
    public static void swap(int[] data,int i,int j){
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    /**
     * 计数排序（Counting Sort）
     * 计算排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
     * 算法描述
     * 找出待排序的数组中最大和最小的元素;
     * 统计数组中每个值为我的元素出现的次数，存入数组Ç的第我项;
     * 对所有的计数累加（从ç中的第一个元素开始，每一项和前一项相加）;
     * 反向填充目标数组：将每个元素我放在新数组的第C（ⅰ）项，每放一个元素就将C（ⅰ）减去1。
     * 算法分析

     * 计数排序是一个稳定的排序算法。当输入的元素是n个0到k之间的整数时，时间复杂度是O（n + k），空间复杂度也是O（n + k），其排序速度快于任何比较排序算法。
     * 当ķ不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
     * @param data
     * @param maxValue
     */
    public static void countingSort(int data[],int maxValue){
        if(ObjectUtils.isEmpty(data)){
            throw new CommonException("data must not be null");
        }
        int[] C = new int[maxValue + 1];
        int len = data.length;
        int sum = 0;
        int[] B = new int[len];
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < len; i++) {
            C[data[i]] += 1;//统计data中各元素的个数，存入C数组
        }
        for (int i = 0; i < maxValue + 1; i++) {
            sum += C[i];
            C[i] = sum;
        }
        for (int i = len - 1; i >= 0; i--) {
            B[C[data[i]] - 1] = data[i];//将data该元素放到排序后数组B中指定的位置
            C[data[i]] --;//将C中该元素-1，方便存放下一个同样大小的元素
        }
        long endTime = System.currentTimeMillis();
        System.out.println();
        System.out.println("计数排序>>>程序运行时间：" + (endTime - startTime) + "ms");
        System.out.println(Arrays.toString(B));
        System.out.println();
    }

    /**
     * 桶排序（Bucket Sort）
     * 桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序（Bucket sort）的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
     * 算法描述
     * 设置一个定量的数组当作空桶;
     * 遍历输入数据，并且把数据一个一个放到对应的桶里去;
     * 对每个不是空的桶进行排序;
     * 从不是空的桶里把排好序的数据拼接起来。
     * 算法分析
     * 桶排序最好情况下使用线性时间为O（n），桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O（n）中。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
     * @param data
     */
    public static void bucketSort(int data[]){
        if(ObjectUtils.isEmpty(data)){
            throw new CommonException("data must not be null");
        }
        long startTime = System.currentTimeMillis();
        int len = data.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            max = Math.max(max,data[i]);
            min = Math.min(min,data[i]);
        }
        //桶数
        int bucketNum = (max - min) / len + 1;
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>(bucketNum);
        for (int i = 0; i < bucketNum; i++) {
            bucketList.add(new ArrayList<Integer>());
        }
        //将每个元素放入桶
        for (int i = 0; i < len; i++) {
            int num = (data[i] - min) / len;
            bucketList.get(num).add(data[i]);
        }
        int k = 0;
        int size = bucketList.size();
        //对每个桶进行排序
        for (int i = 0; i < size; i++) {
            Collections.sort(bucketList.get(i));
            for (int j = 0; j < bucketList.get(i).size(); j++) {
                data[k] = bucketList.get(i).get(j);
                k++;
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println();
        System.out.println("计数排序>>>程序运行时间：" + (endTime - startTime) + "ms");
        System.out.println(Arrays.toString(data));
        System.out.println();
    }


    /**
     * 基数排序（Radix Sort）
     * 基数排序是按照低位先排序，然后收集;再按照高位排序，然后再收集。依次类推，直到最高位有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
     * 算法描述
     * 取得数组中的最大数，并取得位数;
     * ARR为原始数组，从最低位开始取每个位组成基数数组;
     * 对基数进行计数排序（利用计数排序适用于小范围数的特点）;
     * 算法分析
     * 基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O（N）的时间复杂度，而且分配之后得到新的关键字序列又需要O（n）的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O（d * 2n），当然d要远远小于n，因此基本上还是线性级别的。
     * 基数排序的空间复杂度为O（N + K），其中ķ为桶的数量一般来说。N >> K，因此额外空间需要大概Ñ个左右。
     * @param data
     * @param radix
     * @param digits
     * radix表示基数（进制），digits表示最大数值位数
     */
    public static void radixSort(int data[],int radix, int digits){
        if(ObjectUtils.isEmpty(data)){
            throw new CommonException("data must not be null");
        }
        long startTime = System.currentTimeMillis();
        LinkedList<LinkedList> linkedLists = new LinkedList<LinkedList>();
        for (int i = 0; i < radix; i++) {
            LinkedList<Integer> queue = new LinkedList<Integer>();
            linkedLists.offer(queue);//offer用于queue中（Linkedlist同时实现了List和queue接口），add用于List中
        }
        //最大元素的位数,进行digits次分配和收集
        for (int i = 0; i < digits; i++) {
            //分配数组元素
            for (int j = 0; j < data.length; j++) {
                //得到digits的第i+1位
                int r = (int)(data[j] % Math.pow(radix, i + 1) / Math.pow(radix, i));
                LinkedList<Integer> queue2 = linkedLists.get(r);
                queue2.offer(data[j]);
                linkedLists.set(r,queue2);
            }
            //将收集队列元素
            int count = 0;
            for (int j = 0; j < radix; j++) {
                while (linkedLists.get(j).size() > 0){
                    data[count ++] = (Integer) linkedLists.get(j).poll();
                }
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println();
        System.out.println("基数排序>>>程序运行时间：" + (endTime - startTime) + "ms");
        System.out.println(Arrays.toString(data));
        System.out.println();
    }

}
